\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{graphicx}

\begin{document}
\section*{Splines.h}
\subsection*{B-splines}
We need to write the function $B_i^3(x)$,$\frac{d}{d x}B_i^3(x)$ and $\frac{d^2}{d x^2}B_i^3(x)$.

We have two theorems 3.23 and 3.34.
$$B_i^{n+1}(x)=\frac{x-t_{i-1}}{t_{i+n}-t_{i-1}}B_i^n(x)+\frac{t_{i+n+1}-x}{t_{i+n+1}-t_{i}}B_{i+1}^n(x)$$
$$\frac{d}{d x}B_i^n(x)=\frac{n B_i^{n-1}(x)}{t_{i+n-1}-t_{i-1}}-\frac{n B_{i+1}^{n-1}(x)}{t_{i+n}-t_{i}}$$
First, we can derive $B_i^3(x)$ from $B_i^2(x)$ and derive $B_i^2(x)$ from $B_i^1(x)$.

Second, we can derive $\frac{d}{d x}B_i^3(x)$ from $B_i^2(x)$.

Third, we can derive $\frac{d^2}{d x^2}B_i^3(x)$ from $\frac{d}{d x}B_i^2(x)$ and derive $\frac{d}{d x}B_i^2(x)$ from $B_i^1(x)$.
\subsection*{Interpolation}
\subsubsection*{Linear}
The linear interpolation is trivial.Because in the ppForm algorithm we can derive each primary items and constant terms,and in the B-splines algorithm we can find the coefficient of $B_i^1$ is $f(t_i)$ because $B_i^1(t_{i})=1$ and $B_{i}^1(t_{j})=0,j\not =i$.

The following is the cubic,we first explain chase method.
\subsubsection*{Chase Method}
$$
\left[
\begin{matrix}
b_1 & c_1   &       &       &   \\
a_2 & b_2   & c_2   &       &   \\
    & \ddots & \ddots & \ddots &    \\
    &       & a_{n-1} & b_{n-1} & c_{n-1} \\
    &       &       & a_n   & b_n \\
\end{matrix}
\right]
\left[
\begin{matrix}
x_1 \\
x_2 \\
\vdots \\
x_n \\
\end{matrix}
\right]
=
\left[
\begin{matrix}
d_1 \\
d_2 \\
\vdots \\
d_n \\
\end{matrix}
\right]
$$
$$
\left[
\begin{matrix}
b_1 & c_1   &       &       &   \\
a_2 & b_2   & c_2   &       &   \\
    & \ddots & \ddots & \ddots &    \\
    &       & a_{n-1} & b_{n-1} & c_{n-1} \\
    &       &       & a_n   & b_n \\
\end{matrix}
\right]
=
\left[
\begin{matrix}
\alpha_1 &    &       &    &   \\
\gamma_2 & \alpha_2   &    &       &   \\
    & \ddots & \ddots &    &    \\
    &       & \gamma_{n-1} & \alpha_{n-1} &  \\
    &       &       & \gamma_n   & \alpha_n \\
\end{matrix}
\right]
\left[
\begin{matrix}
1   &  \beta_1     &       &    &   \\
    &  1    & \beta_2      &       &   \\
    &       & \ddots &  \ddots  &    \\
    &       &       & 1 & \beta_{n-1} \\
    &       &       &   & 1 \\
\end{matrix}
\right]
$$
$$\alpha_1=b_1,\qquad \beta_1=\frac{c_1}{b_1}$$
$$\gamma_i=a_i,\quad \alpha_i=b_i-\alpha_i\beta_{i-1},\quad \beta_i=\frac{c_i}{\alpha_i},\quad i=2,3,...,n$$
$Ax=d$ is equivalent to $Ly=d$ and $Ux=y$.
$$y_1=\frac{d_1}{b_1},\quad y_i=\frac{d_i-a_i y_{i-1}}{b_i-a_i \beta_{i-1}},\quad i=2,3,...,n$$
$$x_n=y_n,\quad x_i=y_i-\beta_i x_{i+1},i=n-1,n-2,...,1$$
\subsubsection*{ppForm}
According to the Lemma 3.3 and 3.4,
$$\lambda_i m_{i-1}+2m_i+\mu_i m_{i+1}=3\mu_i f[x_i,x_{i+1}]+3\lambda_i f[x_{i-1},x_i]$$
$$\mu_i M_{i-1}+2M_i+\lambda_i M_{i+1}=6f[x_{i-1},x_i,x_{i+1}]$$
$$\mu_i=\frac{x_i-x_{i-1}}{x_{i+1}-x_{i-1}} \quad \lambda_i=\frac{x_{i+1}-x_i}{x_{i+1}-x_{i-1}}$$
So we can derive $m_i$ if the boundary condition is a complete cubic splines and derive $M_i$ if the boundary condition is a cubic spline with specified second derivatives or a natural cubic splines by solving tridiagonal matrix through chase method.

If we have $m_i$ or $M_i$,we can get the cubic,quadratic,linear and constant terms easily.
\subsubsection*{Bsplines method}
By Theorem 3.49,determining $B(X)$ needs $N+2$ basis,so we should determine $N+2$ coefficients.
$$B(x)=\sum_{i=-1}^{N}a_i B_i^3$$
According to $B_i^3(x)$,$\frac{d}{d x}B_i^3(x)$ and $\frac{d^2}{d x^2}B_i^3(x)$,we can get the equation of $f(t_i)$  and $\frac{d}{dx}f(t_i)$ or $\frac{d^2}{d x^2}f(t_i)$.What's more,the coefficient matrix isn't tridiagonal matrix,we should change it into tridiagonal matrix.Through chase method,we can get $a_i$.
\section*{Problems}
\subsection*{A}
Use the boundary complete cubic splines.We run the code so that it will put the coefficients into dataA.txt.Then,plotA.py will read the text and plot the graph.
Problem C,D and E is similar.
\begin{verbatim}
Run:
    ./A N
    py plotA.py
\end{verbatim}
\begin{table}[htbp]
    \centering
    \begin{tabular}{c|cccccc}
        N  &  6 & 11 & 21 & 41 & 81 \\ \hline
        max error  & 0.421705 & 0.0205289 & 0.00316894 & 0.000275356 & 1.609e-05
    \end{tabular}
\end{table}
\begin{figure}[htbp]
    \centering
    \begin{minipage}[t]{0.33\linewidth}
        \centering
        \includegraphics[width=0.95\linewidth]{figure/A.1.png}
        \caption{complete 6 knots}
    \end{minipage}%
    \begin{minipage}[t]{0.33\linewidth}
        \centering
        \includegraphics[width=0.95\linewidth]{figure/A.2.png}
        \caption{complete 11 knots}
    \end{minipage}%
    \begin{minipage}[t]{0.33\linewidth}
        \centering
        \includegraphics[width=0.95\linewidth]{figure/A.3.png}
        \caption{complete 21 knots}
    \end{minipage}%
\end{figure}\begin{figure}[htbp]
    \centering
    \begin{minipage}[t]{0.4\linewidth}
        \centering
        \includegraphics[width=0.95\linewidth]{figure/A.4.png}
        \caption{complete 41 knots}
    \end{minipage}%
    \begin{minipage}[t]{0.4\linewidth}
        \centering
        \includegraphics[width=0.95\linewidth]{figure/A.5.png}
        \caption{complete 81 knots}
    \end{minipage}%
\end{figure}
\subsection*{C}
\begin{verbatim}
Run:
    ./C
    py plotC.py
\end{verbatim}
\begin{figure}[htbp]
    \centering
    \includegraphics[width=0.4\textwidth]{figure/C.1.png}
    \caption{interpolation of B-splines}
\end{figure}
\subsection*{D}
We choose the function $f(x)=\frac{1}{1+x^2}$.
\begin{verbatim}
Run:
    ./D
\end{verbatim}
\begin{table}[htbp]
    \centering
    \begin{tabular}{c|cccccccc}
        x  &  -3.5 & -3 & -0.5 & 0 & 0.5 & 3 & 3.5 \\ \hline
        error & 0.000669568 & 4.71845e-16 & 0.0205289 & 0 & 0.0205289 & 9.71445e-16 & 0.000669568
    \end{tabular}
\end{table}

The points -3, 0, 3 are knots of cubic B-spline,so the error are close to machine precision.I think the cubic may be more accurate.
\subsection*{E}
We express x and y by t.
$$(x,y)=\left(\sqrt{3}\cos{t},\frac{2}{3}(\sqrt{3}\sin{t}+\sqrt{\sqrt{3}|\cos{t}|^{\frac{1}{2}}}\right)$$
where $t\in[-\frac{\pi}{2},\frac{3\pi}{2}]$. 
We can compute the length of the curve from $t_1$ to $t_2$ by divide-and-conquer strategy.(That is,If $|P(t_1),P(\frac{t_1+t_2}{2})|+|P(t_2),P(\frac{t_1+t_2}{2})|<(1+\epsilon)|P(t_1),P(t_2)|$,then choose $|P(t_1),P(\frac{t_1+t_2}{2})|+|P(t_2),P(\frac{t_1+t_2}{2})|$,else,choose the length of curve from $t_1$ to $\frac{t_1+t_2}{2}$ added the length of curve from $\frac{t_1+t_2}{2}$ to $t_2$.)

Thus,we can choose N bisection points of the curve by Newton bisection method.And then we interpolate x and y respectively,we can draw the graph.

\begin{verbatim}
Run:
    ./E N
    py plotE.py
\end{verbatim}
\newpage
\begin{figure}[htbp]
    \centering
    \begin{minipage}[t]{0.33\linewidth}
        \centering
        \includegraphics[width=0.95\linewidth]{figure/E.1.png}
        \caption{complete 10 knots}
    \end{minipage}%
    \begin{minipage}[t]{0.33\linewidth}
        \centering
        \includegraphics[width=0.95\linewidth]{figure/E.2.png}
        \caption{complete 40 knots}
    \end{minipage}%
    \begin{minipage}[t]{0.33\linewidth}
        \centering
        \includegraphics[width=0.95\linewidth]{figure/E.3.png}
        \caption{complete 160 knots}
    \end{minipage}%
\end{figure}
\begin{figure}[htbp]
    \centering
    \begin{minipage}[t]{0.33\linewidth}
        \centering
        \includegraphics[width=0.95\linewidth]{figure/E.4.png}
        \caption{specified 10 knots}
    \end{minipage}%
    \begin{minipage}[t]{0.33\linewidth}
        \centering
        \includegraphics[width=0.95\linewidth]{figure/E.5.png}
        \caption{specified 40 knots}
    \end{minipage}%
    \begin{minipage}[t]{0.33\linewidth}
        \centering
        \includegraphics[width=0.95\linewidth]{figure/E.6.png}
        \caption{specified 160 knots}
    \end{minipage}%
\end{figure}
\begin{figure}[htbp]
    \centering
    \begin{minipage}[t]{0.33\linewidth}
        \centering
        \includegraphics[width=0.95\linewidth]{figure/E.7.png}
        \caption{natural 10 knots}
    \end{minipage}%
    \begin{minipage}[t]{0.33\linewidth}
        \centering
        \includegraphics[width=0.95\linewidth]{figure/E.8.png}
        \caption{natural 40 knots}
    \end{minipage}%
    \begin{minipage}[t]{0.33\linewidth}
        \centering
        \includegraphics[width=0.95\linewidth]{figure/E.9.png}
        \caption{natural 160 knots}
    \end{minipage}%
\end{figure}
We can see that 160 pieces of splines are better.The boundary natural cubic spline is better because the bottom is smoother.
\end{document}